package com.fang.algorithm.leecode;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 成绩最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * <p>
 * 测试用例的答案是一个 32-位 整数。
 * <p>
 * 子数组 是数组的连续子序列
 * <p>
 * 输入: nums = [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * <p>
 * 输入: nums = [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 * @date 2022/5/15 1:36 下午
 **/
public class L152_MaxProduct {
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 3, -4};
        int ans = maxProduct(nums);
        System.out.println(ans);
    }

    private static int maxProduct(int[] nums) {
        int ans = nums[0];
        // 考虑负负得正的情况-2,3,-4 一个dp存储最大值一个dp存储最小值
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(nums[i], dpMax[i - 1] * nums[i]));
            ans = Math.max(ans, dpMax[i]);
        }
        return ans;
    }
}
